#include <iostream>
#include <vector>
#include <list>
using namespace std;

template <class T>
class TNode {
public:
	TNode<T>* _next;
	TNode<T>* _prev;
	T _val;
	TNode(TNode<T>* next=NULL,TNode<T>* prev=NULL,T val=0) {
		_next=next;
		_prev=prev;
		_val=val;
	}
	~TNode() {
	}
};

template <class T>
class TList {
	TNode<T>* _first;
	TNode<T>* _last;
	TNode<T>* _afterLast;
public:
	TList<T> () {
		_first=NULL;
		_last=NULL;
		_afterLast=new TNode<T>;
	}
	TList<T> (const TList<T>& source) {
		if (source._first==NULL) {
			_first=NULL;
			_last=NULL;
			_afterLast=new TNode<T>;
		}
		else {
			TNode<T>* trash=source._first;
			TNode<T>* cpy=new TNode<T>(NULL,NULL,trash->_val);
			TNode<T>* temp;
			_first=cpy;
			while (trash->_next!=NULL) {
				trash=trash->_next;
				temp=cpy;
				cpy=new TNode<T>(NULL,temp,trash->_val);
				temp->_next=cpy;
			} 
			_afterLast=cpy;
			_last=cpy->_prev;
		}
	}
	~TList<T> () {
		if (_first!=NULL) {
			TNode<T>* ptr;
			do {
				ptr=_first;
				_first=_first->_next;
				delete ptr;
			}
			while (_first);
		}
		else
			delete _afterLast;
		_first=NULL;
		_last=NULL;
		_afterLast=NULL;
	}
	bool Empty () const {
		return _first==NULL;
	}
	void Clear() {
		if (_first) {
			TNode<T>* ptr;
			do {
				ptr=_first;
				_first=_first->_next;
				delete ptr;
			} while (_first!=_afterLast);
			_first=NULL;
			_last=NULL;
		}
	}
	bool Push_Back (T val) {
		TNode<T>* _new=new TNode<T> (_afterLast,_last,val);
		if (_new==NULL)
			return false;
		_afterLast->_prev=_new;
		if (this->Empty()) {
			_first=_new;
			_last=_new;
		}
		else {
			_last->_next=_new;
			_last=_new;
		}
		return true;
	}
	bool Push_Front (T val) {
		TNode<T>* _new=new TNode<T> (_first,NULL,val);
		if (_new==NULL)
			return false;
		if (this->Empty()) {
			_first=_new;
			_last=_new;
			_afterLast->_prev=_last;
			_last->_next=_afterLast;
		}
		else {
			_first->_prev=_new;
			_first=_new;
		}
		return true;
	}
	T Pop_Back () {
		if (_first==_last) {
			T a=(_last->_val);
			delete _last;
			_last=NULL;
			_first=NULL;
			_afterLast->_prev=NULL;
			return a;
		}
		T a=_last->_val;
		_last=_last->_prev;
		delete _last->_next;
		_last->_next=_afterLast;
		_afterLast->_prev=_last;
		return a;
	}
	T Pop_Front () {
		if (_first==_last) {
			T a=(_last->_val);
			delete _last;
			_last=NULL;
			_first=NULL;
			_afterLast->_prev=NULL;
			return a;
		}
		_first=_first->_next;
		T a=_first->_prev->_val;
		delete _first->_prev;
		return a;
	}
	TList<T>& operator = (const TList<T>& source) {
		this->~TList();
		if (source._first==NULL) {
			_afterLast=new TNode<T>;
		}
		else {
			TNode<T>* trash=source._first;
			TNode<T>* cpy=new TNode<T>(NULL,NULL,trash->_val);
			TNode<T>* temp;
			_first=cpy;
			while (trash->_next!=NULL) {
				trash=trash->_next;
				temp=cpy;
				cpy=new TNode<T>(NULL,temp,trash->_val);
				temp->_next=cpy;
			} 
			_afterLast=cpy;
			_last=cpy->_prev;
		}
		return *this;
	}
	class TConst_Iterator {
		const TNode<T>* _targ;
	public:
		TConst_Iterator() {
			_targ=NULL;
		}
		TConst_Iterator(const TNode<T>* arg) {
			_targ=arg;
		}
		~TConst_Iterator() {
		}
		TConst_Iterator& operator ++ () {
			_targ=_targ->_next;
			return *this;
		}
		const TConst_Iterator operator ++ (int) {
			TConst_Iterator a=*this;
			_targ=_targ->_next;
			return a;
		}
		TConst_Iterator& operator -- () {
			_targ=_targ->_prev;
			return *this;
		}
		const TConst_Iterator operator -- (int) {
			TConst_Iterator a=*this;
			_targ=_targ->_prev;
			return a;
		}
		const T& operator * () {
			return _targ->_val;
		}
		bool operator == (const TConst_Iterator& rhs) {
			return _targ==rhs._targ;
		}
		bool operator != (const TConst_Iterator& rhs) {
			return _targ!=rhs._targ;
		}
		TConst_Iterator& operator = (TConst_Iterator& rhs) {
			_targ=rhs._targ;
			return *this;
		}

	};
	class TIterator {
		TNode<T>* _targ;
	public:
		TIterator() {
			_targ=NULL;
		}
		TIterator(TNode<T>* arg) {
			_targ=arg;
		}
		~TIterator() {
		}
		TIterator& operator ++ () {
			_targ=_targ->_next;
			return *this;
		}
		const TIterator operator ++ (int) {
			TIterator a=*this;
			_targ=_targ->_next;
			return a;
		}
		TIterator& operator -- () {
			_targ=_targ->_prev;
			return *this;
		}
		const TIterator operator -- (int) {
			TIterator a=*this;
			_targ=_targ->_prev;
			return a;
		}
		T& operator * () {
			return _targ->_val;
		}
		bool operator == (const TIterator& rhs) {
			return _targ==rhs._targ;
		}
		bool operator != (const TIterator& rhs) {
			return (_targ!=rhs._targ);
		}
		TIterator& operator = (const TIterator& rhs) {
			_targ=rhs._targ;
			return *this;
		}
		TNode<T>* _myNode () {
			return _targ;
		}
		operator TConst_Iterator() {
			return TConst_Iterator(_targ);
		}
	};
	TConst_Iterator Begin () const {
		if (_first)
			return TConst_Iterator(_first);
		else
			return TConst_Iterator(_afterLast);
	}
	TIterator Begin () {
		if (_first)
			return TIterator(_first);
		else
			return TIterator(_afterLast);
	}
	TIterator End () {
		return TIterator(_afterLast);
	}
	TConst_Iterator End () const {
		return TConst_Iterator(_afterLast);
	}
	void Swap(TList<T>& rhs) {
		swap(_first,rhs._first);
		swap(_last,rhs._last);
		swap(_afterLast,rhs._afterLast);
	}
	void Errase (TIterator beg, TIterator end) {
		if (beg._myNode()==_first && end._myNode()==_afterLast) {
			this->Clear();
			return;
		}
		if (beg._myNode()==_first) {
			_first=end._myNode();
			end._myNode()->_prev=NULL;
			TIterator ptr=beg;
			for (;beg!=end;) {
				ptr=beg;
				++beg;
				delete ptr._myNode();
			}
			return;
		}
		if (end._myNode()==_afterLast) {
			_last=beg._myNode()->_prev;
			_afterLast->_prev=_last;
			_last->_next=_afterLast;
			TIterator ptr=beg;
			for (;beg!=end;) {
				ptr=beg;
				++beg;
				delete ptr._myNode();
			}
			return;
		}
		TIterator ptr=beg--;
		beg._myNode()->_next=end._myNode();
		end._myNode()->_prev=beg._myNode();
		for (;ptr!=end;) {
			beg=ptr;
			++ptr;
			delete beg._myNode();
		}
	}
	TIterator Insert (TIterator pos, const T& x) {
		if (pos._myNode()==_first)  {
			TNode<T>* _new=new TNode<T>(_first,NULL,x);
			_first->_prev=_new;
			_first=_new;
			return --pos;
		}
		if (pos._myNode()==_afterLast) {
			this->Push_Back(x);
			return --pos;
		}
		TIterator ptr=pos--;
		TNode<T>* t=new TNode<T>(ptr._myNode(),pos._myNode(),x);
		ptr._myNode()->prev=t;
		pos._myNode()->next=t;
		return ++pos;
	}
	void Insert (TIterator pos, size_t n, const T& x) {
                cout << "insert(TIterator pos, size_t n, const T& x)" << endl;
		if (pos._myNode()==_first)  {
			for (int i=0; i<n; ++i) {
				TNode<T>* _new=new TNode<T>(_first,NULL,x);
				_first->_prev=_new;
				_first=_new;
			}
		return;
		}
		if (pos._myNode()==_afterLast) {
			if (_last) {
				for (int i=0; i<n; ++i) {
					TNode<T>* _new=new TNode<T>(NULL,_last,x);
					_last->_next=_new;
					_last=_new;
				}
				_last->_next=_afterLast;
				_afterLast->_prev=_last;
			}
			else {
				TNode<T>* _new=new TNode<T>(NULL,NULL,x);
				_first=_new;
				_last=_new;
				for (int i=1; i<n; ++i) {
					TNode<T>* _new=new TNode<T>(NULL,_last,x);
					_last->_next=_new;
					_last=_new;
				}
				_last->_next=_afterLast;
				_afterLast->_prev=_last;
			}
			return;
		}
		TIterator ptr=pos--;
		for (int i=0; i<n; ++i) {
			//TNode<T> res=new TNode<T>(NULL,pos,x);
			//pos._myNode()->_next=res;
			//++pos;
		}
		pos._myNode()->_next=ptr._myNode();
		ptr._myNode()->_prev=pos._myNode();
	}
	template<class InputIter>
	void Insert (TIterator pos, InputIter first, InputIter last) {
                cout << "insert(TIterator pos, InputIter first, InputIter last)" << endl;
		if (pos._myNode()==_first)  {
			do {
				--last;
				TNode<T>* _new=new TNode<T>(_first,NULL,*last);
				_first->_prev=_new;
				_first=_new;
			} while (last!=first);
			return;
		}
		if (pos._myNode()==_afterLast) {
			TNode<T>* _new;
			if (_last) {
				for (; first!=last; ++first) {
					_new=new TNode<T>(NULL,_last,*first);
					_last->_next=_new;
					_last=_new;
				}
				_last->_next=_afterLast;
				_afterLast->_prev=_last;
			}
			else {
				TNode<T>* _new=new TNode<T>(NULL,NULL,*first);
				_first=_new;
				_last=_new;
				++first;
				for (; first!=last; ++first) {
					TNode<T>* _new=new TNode<T>(_first,NULL,*first);
					_last->_next=_new;
					_last=_new;
				}
				_last->_next=_afterLast;
				_afterLast->_prev=_last;
			}
			return;
		}
		TIterator ptr=pos--;
		for (; first!=last; ++first) {
			TNode<T>* res=new TNode<T>(NULL,pos._myNode(),*first);
			pos._myNode()->_next=res;
			++pos;
		}
		pos._myNode()->_next=ptr._myNode();
		ptr._myNode()->_prev=pos._myNode();
	}
};

int main () {
	TList<int> arr1;
	for (int i=0; i<15; ++i) { 
		arr1.Push_Back(i);		
		arr1.Push_Front(i);														// arr1: 14 13 12 11 ... 11 12 13 14
	}
	for (TList<int>::TConst_Iterator ptr=arr1.Begin(); ptr!=arr1.End(); ++ptr)
		cout << *ptr << ' ';
	cout << endl;
	TList<int> arr2=arr1;														// arr2: 14 13 12 11 ... 11 12 13 14
	TList<int>::TIterator err1=arr1.Begin();
	TList<int>::TIterator err2=arr1.End();
	err1++;
	--err2;
	arr1.Errase(err1,err2);		// arr1 : 14 14	

        // !!!
	arr1.Insert(arr1.Begin(),5U,10);	// arr1 : 10 10 10 10 10 14 14

	vector<int> arr;
	for (int i=30; i<41; ++i)
		arr.push_back(i);														// arr: 30 31 32 ... 39 40
	arr2.Insert(arr2.End(),arr.begin(), arr.end());								// arr2: 14 13 12 11 ... 11 12 13 14 30 31 32 33 34 ... 40
	for (TList<int>::TIterator ptr=arr2.Begin(); ptr!=arr2.End(); ++ptr)
		cout << *ptr << ' ';
	cout << endl;
	arr2.Swap(arr1);															// arr2 : 10 10 10 10 10 14 14 arr1: 14 13 12 11 ... 11 12 13 14 30 31 32 33 ... 40
	for (TList<int>::TIterator ptr=arr2.Begin(); ptr!=arr2.End(); ++ptr)
		cout << *ptr << ' ';
	cout << endl;
	for (TList<int>::TIterator ptr=arr1.Begin(); ptr!=arr1.End(); ++ptr)
		cout << *ptr << ' ';
	cout << endl;
	system("pause");
	return 0;
}
